package com.ztom.top100;

/**
 * 最大正方形
 * <p>
 * https://leetcode-cn.com/problems/maximal-square/
 *
 * @author ZhangTao
 */
public class Code64MaximalSquare {

    public int maximalSquare1(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        int[] max = {0};
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                process(matrix, i, j, max);
            }
        }
        return max[0];
    }

    /**
     * 以 (i, j) 为右下角的最大正方形
     *
     * @param matrix
     * @param i
     * @param j
     * @param max
     * @return
     */
    private int process(char[][] matrix, int i, int j, int[] max) {
        if (matrix[i][j] != '1') {
            return 0;
        }

        if (i == 0 || j == 0) {
            max[0] = Math.max(max[0], 1);
            return 1;
        }
        int p = 1 + Math.min(Math.min(process(matrix, i - 1, j, max), process(matrix, i - 1, j - 1, max)), process(matrix, i, j - 1, max));
        max[0] = Math.max(max[0], p);
        return p;
    }

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }
}
